{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 获取数组中的最大和最小值\n",
    "该方法较之一般的获取数组最大最小值减少了25%的比较次数，原先是一个数比较两次，现在是两个数比较三次"
   ],
   "id": "8887cab39e809653"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T14:31:48.241860Z",
     "start_time": "2024-05-11T14:31:48.235883Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def getMinAndMax(arr: list) -> tuple:\n",
    "    length = len(arr)\n",
    "    Min: int\n",
    "    Max: int\n",
    "    start: int\n",
    "    if length % 2 == 0:\n",
    "        if arr[0] > arr[1]:\n",
    "            Max = arr[0]\n",
    "            Min = arr[1]\n",
    "        else:\n",
    "            Max = arr[1]\n",
    "            Min = arr[0]\n",
    "        start = 2\n",
    "    else:\n",
    "        Max = arr[0]\n",
    "        Min = arr[0]\n",
    "        start = 1\n",
    "    for i in range(start, length):\n",
    "        if arr[i] > arr[i + 1]:\n",
    "            Max = max(Max, arr[i])\n",
    "            Min = min(Min, arr[i + 1])\n",
    "        else:\n",
    "            Max = max(Max, arr[i + 1])\n",
    "            Min = min(Min, arr[i])\n",
    "    return Min, Max"
   ],
   "id": "8077804d91a55d43",
   "outputs": [],
   "execution_count": 23
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 获取数组第i小的元素",
   "id": "32424bbcf23c0615"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "def RandomizedSelect(arr: list, p: int, r: int, i: int) -> int | None:\n",
    "    if p == r:\n",
    "        return arr[p]\n",
    "    q, flag = RandomPartition(arr, p, r)\n",
    "    # q所在的位于整个数组的位置\n",
    "    h = q - p + 1\n",
    "    if i == h:\n",
    "        return arr[q]\n",
    "    elif i < h:\n",
    "        return RandomizedSelect(arr, p, q - 1, i)\n",
    "    else:\n",
    "        return RandomizedSelect(arr, q + 1, r, i - h)\n",
    "\n",
    "\n",
    "def RandomPartition(arr: list, p: int, r: int) -> tuple:\n",
    "    i = random.randint(p, r)\n",
    "    arr[r], arr[i] = arr[i], arr[r]\n",
    "    return Partition(arr, p, r)\n",
    "\n",
    "\n",
    "def Partition(arr: list, p: int, r: int) -> tuple:\n",
    "    cur = p\n",
    "    flag = False\n",
    "    for i in range(p, r):\n",
    "        if arr[i] >= arr[r]:\n",
    "            if arr[i] != arr[r]:\n",
    "                flag = True\n",
    "            arr[i], arr[cur] = arr[cur], arr[i]\n",
    "            cur += 1\n",
    "    arr[cur], arr[r] = arr[r], arr[cur]\n",
    "    # return cur\n",
    "    # return cur if flag or cur != r else (p + r) // 2\n",
    "    return cur, flag or cur != r"
   ],
   "id": "904b6b1dac61d629"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 最坏情况为线性时间的选择算法",
   "id": "6baf210de35398cd"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T14:31:48.290731Z",
     "start_time": "2024-05-11T14:31:48.282952Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def selectMiniNum(arr: list, tar: int) -> int | None:\n",
    "    for i in range(len(arr) // 5):\n",
    "        insertSort(arr[i * 5:i * 5 + 5])\n",
    "    midArr = [arr[i + 2] for i in range(len(arr) // 5)]\n",
    "    mid = RandomizedSelect(midArr, 0, len(midArr) - 1, len(midArr) // 2)\n",
    "    arr[len(arr) - 1], arr[mid * 5 + 2] = arr[mid * 5 + 2], arr[len(arr) - 1]\n",
    "    i, _ = Partition(arr, 0, len(arr) - 1)\n",
    "    if i == tar:\n",
    "        return arr[i]\n",
    "    elif i < tar:\n",
    "        return selectMiniNum(arr[i:], tar - i)\n",
    "    else:\n",
    "        return selectMiniNum(arr[:i - 1], tar)\n",
    "\n",
    "\n",
    "def insertSort(arr: list) -> None:\n",
    "    for i in range(len(arr)):\n",
    "        minded = i\n",
    "        for j in range(i + 1, len(arr)):\n",
    "            if arr[minded] > arr[j]:\n",
    "                minded = j\n",
    "        if i != minded:\n",
    "            arr[i], arr[minded] = arr[minded], arr[i]\n"
   ],
   "id": "93e445ea70a6955a",
   "outputs": [],
   "execution_count": 25
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T14:31:48.297016Z",
     "start_time": "2024-05-11T14:31:48.292365Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr = random.sample(range(100), 100)\n",
    "print(arr[1:5])"
   ],
   "id": "e0ec5d3f34eaed84",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[37, 95, 33, 2]\n"
     ]
    }
   ],
   "execution_count": 26
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "###  设X[1..n]和Y[1..n]为两个数组，每个都包含n个有序的元素。请设计一个O(lgn)时间的算法来找出数组X和Y中所有2n个元素的中位数。\n",
   "id": "8c728de5f43040a5"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T14:44:35.272734Z",
     "start_time": "2024-05-11T14:44:35.266583Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def MidNumberIn2Arr(arr1: list[int], arr2: list[int]) -> int:\n",
    "    a1l = 0\n",
    "    a2l = 0\n",
    "    a1r = len(arr1)\n",
    "    a2r = len(arr2)\n",
    "\n",
    "    while a1l != a1r:\n",
    "        a1m = (a1l + a1r) // 2\n",
    "        a2m = (a2l + a2r) // 2\n",
    "        if arr1[a1m] == arr2[a2m]:\n",
    "            return a1m\n",
    "        elif arr1[a1m] > arr2[a2m]:\n",
    "            a1r = a1m\n",
    "            a2l = a2m + 1\n",
    "        else:\n",
    "            a1l = a1m + 1\n",
    "            a2r = a2m\n",
    "        return min(arr1[a1m], arr2[a2m])"
   ],
   "id": "243f9a2c97745d26",
   "outputs": [],
   "execution_count": 47
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T14:44:54.368503Z",
     "start_time": "2024-05-11T14:44:54.362705Z"
    }
   },
   "cell_type": "code",
   "source": [
    "import random\n",
    "\n",
    "arr1 = [i for i in range(1, 300, 2)]\n",
    "arr2 = [i for i in range(0, 300, 2)]\n",
    "print(MidNumberIn2Arr(arr1, arr2))\n",
    "print(sorted(arr1 + arr2)[149])\n"
   ],
   "id": "ae21c4ec2e299d5f",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "149\n",
      "149\n"
     ]
    }
   ],
   "execution_count": 49
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "![](https://raw.githubusercontent.com/sorhkej/pic-board/main/20240511225211.png?token=APCAT44QD7ZPBB4N74FGJL3GH6DGC)\n",
    "\n",
    "- 若油井的个数是奇数个，则寻找y的中位数作为主管道的位置\n",
    "- 若油井的个数是偶数个，则任意位于两个y中位数的值都可以   "
   ],
   "id": "ab8f9327409688f9"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "",
   "id": "27fc77c7ca188b14"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 在O(N)时间复杂度下求出带权中位数",
   "id": "46185d0d6aad729"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "def SelectWeightedNum(arr: list[(int, float)], tar: int, l: int, r: int) -> int:\n",
    "    if l == r:\n",
    "        return arr[l][0]\n",
    "    p = SelectPartition(arr, l, r)\n",
    "    h = p - l + 1\n",
    "    if h == tar:\n",
    "        return arr[p][0]\n",
    "    elif h > tar:\n",
    "        return SelectWeightedNum(arr, tar, l, p - 1)\n",
    "    else:\n",
    "        return SelectWeightedNum(arr, tar - h, p + 1, r)\n",
    "\n",
    "\n",
    "def SelectPartition(arr: list[(int, float)], l: int, r: int) -> int:\n",
    "    cur = l\n",
    "    for i in range(l, r + 1):\n",
    "        if arr[i][0] * arr[i][1] >= arr[r][0] * arr[r][1]:\n",
    "            arr[i], arr[cur] = arr[cur], arr[i]\n",
    "            cur += 1\n",
    "        arr[cur], arr[r] = arr[r], arr[cur]\n",
    "    return cur"
   ],
   "id": "9558fe1b7f730065"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-05-11T16:12:44.640645Z",
     "start_time": "2024-05-11T16:12:44.635398Z"
    }
   },
   "cell_type": "code",
   "source": [
    "arr = [(1, 0.1), (2, 0.2), (3, 0.3), (4, 0.4)]\n",
    "print(SelectWeightedNum(arr, (len(arr) - 1) // 2, 0, len(arr) - 1))"
   ],
   "id": "1d248288ec2de219",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "execution_count": 83
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
